#include "../../head/myhead.h"

/**
 * *********************************************************************************************************************
 * ************************************************************顺序栈*************************************************
 * *********************************************************************************************************************
 */
// 初始化
void InitStack(SqStack &S)
{
    S.top = -1;
}
// 判空
bool isEmpty(SqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}
bool isEmptyInt(ISqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}
// 进栈
bool push(SqStack &S, char x)
{
    if (S.top == MAXSIZE)
        // 栈满
        return false;
    S.data[++S.top] = x;
    return true;
}
bool pushI(ISqStack &S, int x)
{
    if (S.top == MAXSIZE)
        // 栈满
        return false;
    S.data[++S.top] = x;
    return true;
}
// 出栈,栈顶元素赋值给x
bool pop(SqStack &S, char &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
bool popI(ISqStack &S, int &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
// 读栈顶元素 赋值给x
char getTop(SqStack S)
{
    if (S.top == -1)
        return '\0';
    return S.data[S.top];
    ;
}

bool isLower(char string0, char string1)
{
    int a, b;
    if (string0 == '+' || string0 == '-')
        a = 1;
    if (string0 == '*' || string0 == '/')
        a = 2;
    if (string0 == '(' || string0 == ')')
        a = 3;
    if (string1 == '+' || string1 == '-')
        a = 1;
    if (string1 == '*' || string1 == '/')
        a = 2;
    if (string1 == '(' || string1 == ')')
        a = 3;
    return a < b;
}

/**
 * 计算器
 * n表示字符串数组的长度。字符串数组str只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
 * 整数和运算符之间用一个空格分隔。没有非法表达式。输出计算结果。(精确到小数点后2位)
 * eg: n=5 str[]={"1 + 2"} 输出：3.00
 * n=18 str[]={"4 + 2 * 5 - 7 / 11"}输出13.36
 * ans：
 *  遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，
 *  其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式：
 *      加号：将数字压入栈；
 *      减号：将数字的相反数压入栈；
 *      乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。
 * 补充：int isdigit(int c); 判断参数c是否为数字，返回值：0-不是数字，非0-是数字。
 */
double calculate(char *s)
{
    int n = strlen(s);
    double *stk = (double *)malloc(n * sizeof(double));
    int top = 0;
    char preSign = '+';
    int num = 0;
    for (int i = 0; i < n; ++i)
    {
        if (isdigit(s[i]))
        {
            num = num * 10 + (int)(s[i] - '0');
        }
        if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1)
        { // 若不是符号，或者当前遍历的是倒数第二个元素
            switch (preSign)
            {
            case '+':
                stk[top++] = num;
                break;
            case '-':
                stk[top++] = -num;
                break;
            case '*':
                stk[top - 1] *= num;
                break;
            default:
                stk[top - 1] /= num;
            }
            preSign = s[i];
            num = 0;
        }
    }
    double result = 0;
    for (int i = 0; i < top; i++)
    {
        result += stk[i];
    }
    free(stk);
    return result;
}

/**
 * 王道 3.3.6.01：01.假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，
 * 编写一个算法来判别表达式中的括号是否配对，以字符“\0”作为算术表达式的结束符。
 */
/**
 * 给出一个由左右花括号、中括号、小括号组成的字符串，判断给定字符串的括号是否匹配，括号之间没有优先级
 */
bool isLegalBracket(char str[], int n) // n表示字符串长度,str存字符串
{
    char ch[MAXSIZE];
    // 字符栈
    int top = -1;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '{' || str[i] == '[' || str[i] == '(')
            // 左括号直接入栈
            ch[++top] = str[i];
        // 如果执行else if 那么必然是右括号，所以如果符号栈空，必然是失配
        // 四种失配情况，栈空失配，大括号失配，中括号失配，小括号失配
        else if (top == -1 ||
                 (str[i] == '}' && ch[top] != '{') ||
                 (str[i] == ']' && ch[top] != '[') ||
                 (str[i] == ')' && ch[top] != '('))
            return 0;
        else
            top--;
    }
    if (top != -1)
        return 0;
    return 1;
}

/**
 * 有一个字符串，由左括号'('和右括号')'组成，保证输入的括号匹配性是合法的。
 * 每一对括号都有价值，深度 为1的括号，价值为1，深度为2的括号价值为2，求该序列的所有对括号的价值和。
 * 例如："((()))"，这三对 括号的深度分别为1、2、3，则价值和为6。
 *      "()(())"，这三对括号的深度分别为1、1、2，则价值和为4.
 *  eg: 输入："((()))(())" 输出：9
 *      输入："()()()()"输出4
 */
int bracketValue()
{
    int ans;  // 本题的答案
    int deep; // 记录深度
    char str[MAXSIZE];
    scanf("%s", str);
    int len = strlen(str); // 输入的字符串的长度
    for (int i = 0; i < len; i++)
    {

        if (str[i] == '(')
            // 如果是左括号则深度+1
            deep++;
        else // 右括号则计算该对括号的价值，并深度-1
        {
            ans += deep;
            deep--;
        }
    }
    cout << ans << endl;
    return 0;
}

/**
 * 栈模拟：给定输入序列和输出序列，判断通过栈能否得到输出序列，对于输入序列，随时可以入栈或者出栈
 * 思路：1.创建一个数组stack[]，模拟栈
 *      2.遍历数组 pushed，将 pushed 的每个元素依次入stack[]；
 *      3.每次将 pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈，
 *   同时遍历数组 popped，直到栈为空或栈顶元素与 popped 的当前元素不同。
 *      4.如果栈为空，返回 true，否则，返回false
 */
bool validateStackSequences(int *pushed, int pushedSize, int *popped, int poppedSize)
{
    int *stk = (int *)malloc(sizeof(int) * pushedSize);
    int top = 0;
    for (int i = 0, j = 0; i < pushedSize; i++)
    {
        stk[top++] = pushed[i];
        while (top > 0 && stk[top - 1] == popped[j])
        {
            top--;
            j++;
        }
    }
    free(stk);
    return top == 0;
}

bool isLegalStackOrder(string s)
{
    int n = s.size(), top = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'I')
            top++;
        else if (s[i] == 'O')
        {
            if (top == 0)
                return false;
            top--;
        }
    }
    return true;
}

/**
 * 用两个栈来实现队列，请写出入队和出队算法。
 * 思路：
 * 将一个栈当作输入栈，用于压入 appendTail 传入的数据；另一个栈当作输出栈，用于 deleteHead 操作。
 * 每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，
 * 这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序
 */
typedef struct
{
    int *stk;
    int stkSize;
    int stkCapacity;
} Stack;

Stack *stackCreate(int cpacity)
{
    Stack *ret = (Stack *)malloc(sizeof(Stack));
    ret->stk = (int *)malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}

void stackPush(Stack *obj, int value)
{
    obj->stk[obj->stkSize++] = value;
}

void stackPop(Stack *obj)
{
    obj->stkSize--;
}

int stackTop(Stack *obj)
{
    return obj->stk[obj->stkSize - 1];
}

bool stackEmpty(Stack *obj)
{
    return obj->stkSize == 0;
}

void stackFree(Stack *obj)
{
    free(obj->stk);
}

typedef struct
{
    Stack *inStack;
    Stack *outStack;
} CQueue;

CQueue *cQueueCreate()
{
    CQueue *ret = (CQueue *)malloc(sizeof(CQueue));
    ret->inStack = stackCreate(10000);
    ret->outStack = stackCreate(10000);
    return ret;
}

void in2out(CQueue *obj)
{
    while (!stackEmpty(obj->inStack))
    {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}

void cQueueAppendTail(CQueue *obj, int value)
{
    stackPush(obj->inStack, value);
}

int cQueueDeleteHead(CQueue *obj)
{
    if (stackEmpty(obj->outStack))
    {
        if (stackEmpty(obj->inStack))
        {
            return -1;
        }
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}

void cQueueFree(CQueue *obj)
{
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}

/**
 * 将一个十进制的正整数n转换为k进制的数
 * 思路：定义一个栈，若a = n%k，将a入栈，n/=k，如此循环直到a = 0；然后将
 */
void tenToK(int n, int k)
{
    int ansStack[MAXSIZE];
    int top = -1;
    while (n)
    {
        ansStack[++top] = n % k;
        n /= k;
    }
    while (top != -1)
    {
        printf("%d", ansStack[top]);
        top--;
    }
}

/**
 * 火车站：
 * 有一列火车车厢进站，可以通过中转站改变出站顺序，
 * 现在的问题是，给定入站顺序和出栈顺序后，请问该站的容纳量至少为多少节车厢？
 * 例如，进站顺序为ABCD，出站顺序为DCBA，则该站台的容纳量至少为4.保证出站顺序合法
 * 第一行输入n，表示总共有n节车厢
 * 第二行输入n个字母表示进站的车厢序列
 * 第三行输入n个字母表示出站的车厢序列输出x表示站台的容纳量
 * 输入： 5 ABCDE CBEDA 输出：3
 * 思路：
 * 方法一： 1.定义一个长度为n的char数组，作为栈，和当前车站容量temp，以及答案ans
 *          2.遍历in，并将数据存入栈中
 *          3.若栈顶元素与out中的元素相同这循环弹出栈中元素，直到栈空或者不相等为止
 *          4.若栈空，则将temp和ans比较若temp>ans,则更新ans为temp。
 *          5.若栈空temp=0
 */
int minTrainStations(int n, char *in, char *out)
{
    char *stk = (char *)malloc(n * sizeof(char));
    int ans = 0, temp = 1, top = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        stk[top++] = in[i];
        temp++;
        while (top > 0 && stk[top - 1] == out[j])
        {
            top--;
            temp--;
            j++;
        }
        if (temp > ans)
            ans = temp;
    }
    return ans;
}

/**
 * 求后缀表达式的值
 * 思路：使用一个栈存储操作数，从左到右遍历表达式，进行如下操作：
 *          1.如果遇到操作数，则将操作数入栈；
 *          2.如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，
 * 使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
 */
bool isNumber(char *token)
{
    return strlen(token) > 1 || ('0' <= token[0] && token[0] <= '9'); // 长度大于1的肯定是数字
}
int evalRPN(char **tokens, int tokensSize)
{
    int n = tokensSize;
    int *stk = (int *)malloc(n * sizeof(int)), top = 0;
    for (int i = 0; i < n; i++)
    {
        char *token = tokens[i];
        if (isNumber(token))
        {
            stk[top++] = atoi(token);
        }
        else
        {
            int num2 = stk[--top];
            int num1 = stk[--top];
            switch (token[0])
            {
            case '+':
                stk[top++] = num1 + num2;
                break;
            case '-':
                stk[top++] = num1 - num2;
                break;
            case '*':
                stk[top++] = num1 * num2;
                break;
            case '/':
                stk[top++] = num1 / num2;
                break;
            }
        }
    }
    return stk[top - 1];
}

/**
 * 王道练习题：3.1.4（二）：04判断链表的全部n个字符是否中心对称(假设链表带头节点)
 * 遍历链表前半部分逐个入栈，到链表中间位置后，将栈中元素出栈，逐个与链表后半部分比较。
 * 若全部一致则是中心对称，
 * 否则不是中心对称。
 */
bool isSymmetrical(LNode *L, int n)
{
    if (n < 1)
        return false;
    if (n == 1)
        return true;
    stack<int> s;
    LNode *p = L->next;
    int i;
    for (i = 0; i < n / 2; i++)
    {
        s.push(p->data);
        p = p->next;
    }
    if (n % 2 == 1)
        p = p->next;
    while (p != NULL && !s.empty())
    {
        int temp = s.top();
        if (temp != p->data)
            return false;
        s.pop();
        p = p->next;
    }
    if (s.empty())
        return true;
    else
        return false;
}

/**
 * *********************************************************************************************************************
 * ************************************************************链栈(默认带头结点)*************************************************
 * *********************************************************************************************************************
 */
// 初始化
void InitLStack(LStack *L)
{
    L = (LStack *)malloc(sizeof(LNode));
    L->next = NULL;
}
// 判空
bool isEmptyL(LStack *L)
{
    if (L->next == NULL)
        return 1;
    else
        return 0;
}
// 进栈
void pushL(LStack *L, int x)
{
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode));
    p->next = NULL;
    p->data = x;
    // 头插法
    p->next = L->next;
    L->next = p;
}
// 出栈
bool popL(LStack *L, int &x)
{
    if (L->next == NULL)
        return 0;
    LNode *p;
    p = L->next;
    x = p->data;
    L->next = p->next;
    // 删除链表第一个结点
    free(p);
    return 1;
}

/**
 * *********************************************************************************************************************
 * **************************************************************队列***************************************************
 * *********************************************************************************************************************
 */
/**
 * 王道 3.2.5.01：若希望循环队列中的元素都能得到利用，
 * 则需设置一个标志域 tag，并以 tag 的值为 0或1来区分队头指针 front 和队尾指针rear
 * 相同时的队列状态是“空”还是“满”.试编写与此结构相应的入队和出队算法。
 *
 * 当有元素入队时tag置为1,出队时置为0；
 * 因为只有入队操作可能导致队满，只有出队操作导致队空
 * 执行入队操作时，根据tag判断之前一次操作是出队还是入队，
 *      若tag = 0，说明之前一次操作是出队，队列必然有空位，可以执行入队
 *      若tag = 1，说明之前一次操作是入队，需要根据front == rear来判断此时队列是否为满
 * 执行出队操作时，根据tag判断之前一次操作是出队还是入队，
 *      若tag = 0，说明之前一次操作是出队，需要根据front == rear来判断此时队列是否为空
 *      若tag = 1，说明之前一次操作是入队，队列必然有元素，可以执行出队
 */
bool enQue(STQueue &Q, int x)
{
    if (Q.tag == 1 && Q.front == Q.rear) // 队满
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    Q.tag = 1;
    return true;
}
bool outQue(STQueue &Q, int x)
{
    if (Q.tag == 0 && Q.front == Q.rear) // 队空
        return false;
    Q.data[Q.front] = x;
    Q.front = (Q.front + 1) % MAXSIZE;
    Q.tag = 0;
    return true;
}

/**
 * 王道 3.2.5.02：Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。
 * 思路：定义一个栈，队列每个元素逐个出队同时入栈，然后逐个出栈然后入队
 */
// void reverse(Stack &S, queue &Q)
// {
    
//     while (!QueueEmpty(Q))
//     {
//         x = DeQueue(Q);
//         Push(S, x);
//     }
//     while (!StackEmpty(S))
//     {
//         Pop(S, x);
//         EnQueue(Q : x);
//     }
// }

/**
 * 王道 3.2.5.03：
 * 利用两个栈 S1和S2来模拟一个队列，已知栈的4个运算定义如下:
 * Push(S,x);       //元素x入栈S
 * PoP(S,x);        //S出栈并将出栈的值赋给x
 * StackEmpty(S);   //判断栈是否为空
 * StackOverflow(S);//判断栈是否满
 * 如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)?
 * //将元素x入队                Enqueue;
 * //出队，并将出队元素存储在x中    Dequeue;
 * //判断队列是否为空           QueueEmpty;
 */
// bool isQueueEmpty(Stack s1, Stack s2)
// {
//     return stackEmpty(s1) && stackEmpty(s2) ? true : false;
// }
// int enQueue(ISqStack &s1, ISqStack &s2, int x)
// {
//     if (!StackOverflow(S1))
//     {
//         Push(S1, e);
//         return 1;
//     }
//     if (StackOverflow(Sl) && !stackEmpty(s2))
//     {
//         print£("队列满");
//         return 0;
//     }
//     if (StackOverflow(S1) && StackEmpty(S2))
//     {
//         while (!StackEmpty(sl))
//         {
//             Pop(S1, x);
//             Push(S2, x);
//         }
//     }
//     Push(S1, e);
//     return 1;
// }
// int deQueue(ISqStack &s1, ISqStack &s2, int &x)
// {
//     if (isQueueEmpty(s1, s2))
//         return 0;
//     if (!isEmptyInt(s2))
//         popI(s2, x);
//     else
//     {
//         while (!isEmptyInt(s1))
//         {
//             popI(s1, x);
//             pushI(s2, x);
//         }
//         popI(s2, x);
//     }
//     return 1;
// }

/**
 * 王道 3.2.5.04【2019 统考真题】
 * 请设计一个队列，要求满足:
 * ①初始时队列为空;
 * ②入队时，允许增加队列占用空间:
 * ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减;
 * ④入队操作和出队操作的时间复杂度始终保持为0(1)。
 * 请回答:
 *      1)该队列是应选择链式存储结构，还是应选择顺序存储结构?
 *      2)画出队列的初始状态，并给出判断队空和队满的条件。
 *      3)画出第一个元素入队后的队列状态。
 *      4)给出入队操作和出队操作的基本过程。
 * 题目要求要允许增加队列占用空间，所以应选择链式存储结构，，
 */

int main()
{
    // 计算器
    //  char str[]={"4 - 7 / 11 + 2 * 5"};
    //  double ans = calculate(str);
    //  printf("%.2lf",ans);
    // 火车站
    //  int n;
    //  cin>>n;
    //  char* in = (char*)malloc(n * sizeof(char));
    //  char* out = (char*)malloc(n * sizeof(char));
    //  cin>>in;
    //  cin>>out;

    // char in[4] = {'A', 'B', 'C', 'D'};
    // char out[4] = {'D', 'C', 'B', 'A'};
    // char in[5]={'A','B','C','D','E'};
    // char out[5]={'C','B','E','D','A'};
    // int ans = minTrainStations(4, in, out);
    // cout << ans << endl;

    // string s = "IOIIOIOO";
    string s = "IOOIOIIO";
    bool TAG = isLegalStackOrder(s);
    cout << TAG << endl;
    // system("pause");
    return 0;
}